package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         131,
		Discription: "将字符串分割成若干子串，使得每个子串都是回文",
		Level:       2,
		Labels: map[string]int{
			"动态规划": 1,
			"递归":   1,
		},
	})
}

func PartitionStr(s string) [][]string {
	length := len(s)
	//dp[i][j]表示s[i:j]是否构成回文串
	dp := make([][]bool, length)
	for i := 0; i < length; i++ {
		dp[i] = make([]bool, length+1)
		for j := 0; j <= i+1; j++ {
			dp[i][j] = true
		}
	}

	//i从后开始往前遍历！！！
	for i := length - 2; i >= 0; i-- {
		for j := i + 2; j <= length; j++ {
			dp[i][j] = dp[i+1][j-1] && s[i] == s[j-1]
		}
	}

	res := make([][]string, 0)
	strs := make([]string, 0)
	var dfs func(int)
	dfs = func(start int) {
		if start == length {
			res = append(res, append([]string(nil), strs...))
			return
		}

		for j := start + 1; j <= length; j++ {
			if dp[start][j] {
				strs = append(strs, s[start:j])
				dfs(j)
				strs = strs[:len(strs)-1]
			}
		}
	}

	dfs(0)
	return res
}
